COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	{≤G⊂CαLOCUS SOLVING.λ30P90I425,0JCFA} SECTION 9.
C00006 00003	⊂9.1	Parallax and the Camera Model.⊃
C00007 00004	{QW0,1260,0,1900I200,0}⊂9.2	Camera Locus Solving: One View of Three Points⊃
C00010 00005	{W0,750,100,1900λ25JUFA}
C00013 00006	
C00017 00007
C00020 00008	
C00022 00009
C00025 00010	⊂9.3	System Locus Solving: Two Views of Many Points.⊃
C00028 ENDMK
C⊗;
{≤G;⊂C;αLOCUS SOLVING.;λ30;P90;I425,0;JCFA} SECTION 9.
{JCFD}  CAMERA AND FEATURE LOCUS SOLVING.
{λ10;W250;JAFA}
	9.0	Introduction to Locus Solving.
	9.1	Parallax and the Camera Model.
	9.2	Camera Locus Solving: One View of Three Points.
	9.3	System Locus Solving: Two Views of Many Points.
	9.4	Object Locus Solving: Silhouette Cone Intersection.
	9.5	Sun Locus Solving: A Simple Solar Emphemeris.
	
{λ30;W0;I950,0;JUFA}
⊂9.0	Introduction to Locus Solving.⊃

	There  are three  kinds  of  locus  solving problems  in  the
geometry  of computer  vision: camera locus  solving,   feature locus
solving and sun locus solving. Camera solving is  routinely attempted
in two ways: using  one image the 2-D image loci of  a set of already
known  3-D world  loci (perhaps points  on a  calibration object) are
measured and a camera model  computed; or using two or more  images a
set  of corresponding  landmark feature  points are  found  among the
images and the whole system is  solved relative to itself. After  the
camera positions are  known, the location  and extent of  the objects
composing the scene  can be found using parallax (motion parallax and
stereo parallax). Parallax is the principal means of depth perception
and is  the outstanding  alchemist for  converting leaden  2-D images
into  golden 3-D  models. After the  camera and  object positions are
known to some  accuracy,   the nature and  location of light  sources
might  potentially be  deduced  from the  shines and  shadows  in the
images. However, in  outdoor situations the  primary light source  is
the sun,  whoes position in  the sky can  be computed from  the time,
date, latitude and longitude by means of a simple emphemeris.{Q}
⊂9.1	Parallax and the Camera Model.⊃

Lens Center Irrelevancy Theorem.

	The actual location of the principal axis of the lens in the
image is irrelevant because the affect of deviation from the center
is equivalent to rotating the camera.
{Q;W0,1260,0,1900;I200,0;}⊂9.2	Camera Locus Solving: One View of Three Points⊃
{FC}	 - The Iron Triangle Camera Solving Method.{FA;λ30;}
	A mobile  robot having only visual  perception must  determine
where it is going by what it sees.  Specifically, the position of the
robot is found  relative to the  position of the  lens center of  its
camera. The following  algorithm is a geometric  method for computing
the locus of a camera's lens center from three landmark points.
{I∂500,0;}
	Consider  four non-coplanar points A,  B, C  and L.  Let L be
the unknown camera's lens center, here after to be  called the camera
locus,  also let A,  B and C be the landmark points whoes loci either
are given on  a map or  are found  by stereo from  two already  known
viewing positions.  Assuming for the moment an ideal camera which can
see  all 4π  steradians at  once, the camera  can measure  the angles
formed by the rays from the camera locus to the landmark points.  Let
these angles be called  ≤a≥, ≤b≥ and ≤g≥ where ≤a≥  is the angle BLC,
≤b≥  is the  angle ALC  and ≤g≥ is  the angle  ALB.   The camera also
measures whether the landmarks  appear to be in clockwise  or counter
clockwise order as seen from L. If the landmarks are counterclockwise
then B is swaped with C and ≤b≥ with ≤g≥. A mechanical analog of  the
problem would be to position a rigid  triangular piece of sheet metal
between the legs of  a tripod so that its corners touch each leg. The
metal triangle is the same size  as the triangle ABC and the legs  of
the tripod are rigidly held forming  the angles ≤a≥, ≤b≥ and ≤g≥. The
algorithm was developed by thinking in terms of this analogy.
{L100,130;H3;X0.8;*IRONT.PLT;FD;
L100,130;I∂80,∂-280;}A{
L100,130;I∂-225,∂-130;}B{
L100,130;I∂270,∂-110;}C{
L100,130;I∂0,∂410;}L{
W0,1260,100,1800;FA;Q;λ10;}
{W0,750,100,1900;λ25;JUFA}
\In order to put the iron triangle
into the tripod, the  edge BC is first placed
between the tripod legs of angle ≤a≥.  Let
a  be the length of BC, likewise b and c
are the lengths of AC and AB.


\Restricting attention to the plane LBC,
consider the locus of points L' arrived at
by sliding the  tripod  and  maintaining
contacts at B and C.


\Recalling  that  in  a  circle,  a chord
subtends equal angles at any two  points
on   the   same  one  of  the  two  arcs
determined by the chord; it can be  seen
that  the  set of possible L' points lie
on a  circular  arc.  Let  this  arc  be
called  L's  arc,  which  is part of L's
circle.



\Also in a circle the angle at the center
is   double    the    angle    at    the
circumference, when the rays forming the
angles meet  the  circumference  in  the
same two points.





\And  the  perpendicular  bisector  of  a
chord passes  thru  the  center  of  the
chord's  circle  bisecting  the  central
angle. Let S be the distance between the
center of the circle and the chord BC.
So by trigonometric definitions:
{JC} R  =  a / 2sin(≤a≥)
{JC} S  =  R cos(≤a≥)
{H3;
L400,500;C5;
I∂-80,∂-138.56;C5;V∂160,∂0;C5;

L400,100;C160;C5;
I∂-80,∂-138.56;C5;V∂160,∂0;C5;

L400,-300;C160;C5;
I∂-80,∂-138.56;C5;V∂160,∂0;C5;

L400,-700;C160;C5;
I∂-80,∂-138.56;C5;V∂160,∂0;C5;

W0,1260,100,1800;λ30;Q}

The position of L on its arc in the plane BLC can be expressed in
terms  of  one  parametric  variable omega ≤w≥,  where ≤w≥ is the counter
clockwise  angular  displacement  of  L  from  the  perpendicular
bisector such that for ≤w≥=π-≤a≥ L is at B and for ≤w≥=≤a≥-π L is at C.
By spinning the iron triangle about the axis BC, the vertex A sweeps
a circle

Let  H  be  the  radius  of  A's circle and let D be the directed
distance between te center of A's circle and the midpoint of  BC.
By Trigonometric relations on the triangle ABC:

	cos(ACB) = (a↑2 + b↑2 - c↑2)/2ab
	sin(ACB) =  sqrt(1 - cos(C)↑2)
	H = b sin(ACB)
  	D = b cos(ACB)  -  a/2

Now consider the third leg of the tripod which forms the angles ≤b≥
and ≤g≥.   The  third  leg intersects the BLC plane at point L and
extends into the  appropriate  halfspace  so  that  the  landmark
points  appear to be in clockwise order as seen from L. Let A' be
the third leg's point of intersection with the  plane  containing
A's circle.

Let the distance between the point  A'  and  the  center  of  A's
circle  less  the radius H of A's circle be called "The Gap". The
gap's value is negative if A' falls within A's circle.

By constructing an expression for the  value  of  the  Gap  as  a
function of the parametric variable ≤w≥, a root solving routine can
find the ≤w≥ for  which  the  gap  is  zero  thus  determining  the
orientation  of  the  triangle  with respect to the tripod and in
turn the locus of the point L in space.

	Using vector geometry, place an origin at the midpoint of BC,
establish the unit y-vector j pointing towards the vertex B,  let the
plane BCL be the  x-y plane and orient  the unit x-vector i  pointing
into L's halfplane.  For right handedness, set the unit z-vector k to
i cross j. In the newly defined coordinates points B, C, and L become
the vectors:{JV;λ10;}
	B  =  (-s, +a/2, 0);
	C  =  (-s, -a/2, 0)
	L  =  (R cos(w), R sin(w), 0)
Introducing two unknowns xx and zz the locus of point A' as a vector is:
	A'  =  (xx, D, zz)
The vectors corresponding to the legs of the tripod are:
	LB  =  B - L  = (-s-Rcos(w), +a/2-Rsin(w), 0)
	LC  =  C - L  = (-s-Rcos(w), -a/2-Rsin(w), 0)
	LA  =  A'- L  = (xx-Rcos(w),    D-Rsin(w), zz)
Since the third leg forms the angles ≤b≥ and ≤g≥:
	LA . LC = |LA| |LC| cos(≤b≥)
	LA . LB = |LA| |LB| cos(≤g≥)
Solving each equation for |LA| yields:
	|LA| = (LA . LC)/|LC|cos(≤b≥)  =  (LA . LB)/|LB|cos(≤g≥)
Multiplying by |LB| |LC| cos (≤b≥) cos (≤g≥) gives:
	(LA . LC)|LB| cos(≤g≥) = (LA . LB)|LC| cos(≤b≥)
Expressing the vector quantites in terms of their components:
	|LB| = sqrt((-S-Rcos(w))↑2 + (+a/2-Rsin(w))↑2)
	|LC| = sqrt((-S-Rcos(w))↑2 + (-a/2-Rsin(w))↑2)
	LA . LC = (xx-Rcos(w))(-s-Rocs(w)) + (D-Rsin(w))(-a/2-Rsin(w))
	LA . LC = (xx-Rcos(w))(-s-Rocs(w)) + (D-Rsin(w))(+a/2-Rsin(w))
Substituting:
	((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(-a/2-Rsin(w)))  |LB|cos(≤g≥)
   =	((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(+a/2-Rsin(w)))  |LC|cos(≤b≥)

The previous equation is linear in xx, so solving for xx:
	xx = P/Q + Rcos(w)
where
	P = (-s-Rcos(w))(|LB|cos(≤g≥) - |LC|cos(≤b≥))
	Q = (D-Rsin(w))((+a/2-Rsin(w))|LC|cos(≤b≥) 
		- (-a/2-Rsin(w))|LB|cos(≤g≥))
The unknown zz can be found from the definition of |LA|
	|LA|  =  sqrt( (xx-Rcos(w))↑2  +  (D-Rsin(w))↑2  +  zz↑2)
so 	zz    = sqrt( |LA|↑2  - (P/Q)↑2  - (D-Rsin(w))↑2)
and since:
	|LA| = (LA . LC) / |LC|cos(≤b≥)
The negative values of zz are precluded by the clockwise ordering
of  the  landmark  points. Thus the expression for the Gap can be
formed:
	
	GAP = sqrt( (XX+S)↑2 + zz↑2 )  - H

As mentioned above, when the gap is zero the  problem  is  solved
since the locus of A' then must be on A's circle, so the triangle
touches the third leg. The gap function looks like a cubic on its
interval  [≤a≥-π,π-≤a≥], and it usually crosses zero just once.

Having  found  the locus of L in the specially defined coordinate
system all that remains to do is to solve for the components of L
in  the  coordinate  system  that A, B and C were given.  This is
done by  considering  three  vector  expressions  which  are  not
dependent  on the frame of reference and do not have second order
L terms, namely: (CA dot CL); (CB dot CL); and ((CA x CB) dot CL).
Let the locus of L in the given frame of reference be (X,Y,Z) and
let the components  of  the  points  A,  B and C  be  (XA,YA,ZA),
(XB,YB,ZB) and (XC,YC,ZC) respectively.  Listing all four points in
both frames of reference:{λ10;JA}
	A	= (xx,    D,   zz)	=   (XA, YA, ZA)
	B	= (-s, +a/2,    0)	=   (XB, YA, ZA)
	C	= (-s, -a/2,    0)      =   (XC, YC, ZC)
	L	= (Rcos(w),Rsin(w),0)	=   ( X,  Y,  Z)
Evaluating the vector expressions which are invariant:
	CA = A - C				=   (XA-XC. YA-YC, ZA-ZC)
	CB = B - C = (0, a, 0)		        =   (XB-XC, YB-YC, ZB-ZC)
	CL = L - C = (Rcos(w)+s,Rsin(w)+a/2,0)	=   ( X-XC,  Y-YC,  Z-ZC)

	CA . CL = (xx+S)(Rcos(w)+s)+(D+a/2)(Rsin(w)+A/2)
		= (XA-XC)(X-XC) + (YA-YC)(Y-YC) + (ZA-ZC)(Z-ZC)

	CB . CL	= a(Rsin(w) + a/2)
		= (XB-XC)(X-XC) + (YB-YC)(Y-YC) + (ZB-ZC)(Z-ZC)

	(CA x CB) . CL = -a zz(Rcos(w) + s)
		       =  ((YA-YC)(ZB-ZC) - (ZA-ZC)(YB-YC)) (X-XC)
		        - ((XA-XC)(ZB-ZC) - (ZA-ZC)(XB-XC)) (Y-YC)
			+ ((XA-XC)(YB-YC) - (YA-YC)(XB-XC)) (Z-ZC)

The last three  equations  are  linear  equations  in  the  three
unknowns X, Y & Z which are readily isolated by Cramer's Rule.
⊂9.3	System Locus Solving: Two Views of Many Points.⊃

⊂9.4	Object Locus Solving: Silhouette Cone Intersection.⊃

⊂9.5	Sun Locus Solving: A Simple Solar Emphemeris.⊃